Numerous data streams exist that may be harnessed for analytics and reporting. A data stream management system (“DSMS”) may be provided with a query plan that dictates how the DSMS will capture and process data from a data stream. As query plans become more complex, they require more resources such as memory and CPU processing time.
One type of complex query plan is a directed acyclic graph (“DAG”) query plan. A DAG query plan includes two or more operators that are executed in parallel. DAG query plans introduce issues that are not found in linear query plans. For example, DAG query plans often include operators with multiple fan-in connections, such as multi-way joins and union operators. Those operators typically process input stream tuples (i.e., the operator performs some function involving the tuples as input) in the order of their timestamps, irrespective of the connections from which the tuples arrive. Thus, a tuple may have to wait for the arrival of other tuples before being processed by a join operator. This forced delay may be referred to as input delay synchronization (“IDS”).
Another issue arises where a DAG query plan has an operator with multiple fan-out connections. For example, copy operators are used to duplicate shared output. The same output tuples need to be passed to multiple down stream operators. The output tuples should not be dropped until processed by all downstream operators. This may be referred to as shared output synchronization (“SOS”).
For purposes of optimizing a query plan to reduce memory and CPU consumption, DAG query plans like may be partitioned into segments as basic units for scheduling. At runtime, however, the effectiveness of such optimization may be reduced where IDS causes multiple-input operators to block and delay progression of tuples through the segments. Additionally, SOS requires synchronized scheduling of query segments that share the same stream input. Although tuples may be processed in batches, as batch size increases, longer idle time may be required for IDS and a larger buffer may be required for SOS.